package leetcode;

/**
 * Created by Ghost on 2015/2/18.
 */
public class Binary_Tree_Maximum_Path_Sum {
    public int max = Integer.MIN_VALUE;
    public int findRst(TreeNode root){
        if (root == null) {
            return 0;
        } else {
            int sumLeft = findRst(root.left);
            int sumRight = findRst(root.right);
            int cur = root.val;
            int leftRightSum = sumLeft+cur+sumRight;
            max = max<leftRightSum?leftRightSum:max;
            int subMax = sumLeft > sumRight ? sumLeft : sumRight;

            if (cur+subMax > 0) {
                if(max<subMax+cur)
                    max = subMax+cur;
                return cur + subMax;
            } else {
                return 0;
            }
        }
    }
    public int maxPathSum(TreeNode root) {
        if(root==null)
            return 0;
        max = max<root.val?root.val:max;
        findRst(root);
        return max;
    }

    public static void main(String[] args){
        Binary_Tree_Maximum_Path_Sum binary_tree_maximum_path_sum = new Binary_Tree_Maximum_Path_Sum();
        TreeNode root = new TreeNode(2);
       root.left = new TreeNode(-1);
       /* root.left.left = new TreeNode(-4);
        root.left.right = new TreeNode(99);
        root.right = new TreeNode(-3);
        root.right.left = new TreeNode(-5);
        root.right.right = new TreeNode(-6);*/
        System.out.println(binary_tree_maximum_path_sum.maxPathSum(root));
    }
}
